package nmf;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

/**
 * Sparse Matrix
 *
 */
public class SparseMatrix {
   
   /**
    * A coordinate in sparse matrix
    */
   public class Coordinate {
      int row = 0;
      int col = 0;
      double element = 0;
      
      public Coordinate(final int row, final int col, final double element) {
         this.row = row;
         this.col = col;
         this.element = element;
      }
      
      @Override
      public int hashCode() {
         int hash = 7;
         hash = 53 * hash + row;
         hash = 53 * hash + col;
         return hash;
      }
      
      @Override
      public boolean equals(final Object o) {
         if (!(o instanceof Coordinate)) {
            return false;
         }
         
         final Coordinate c = (Coordinate) o;
         if (row == c.row && col == c.col) {
            return true;
         }
         
         return false;
      }
   }
   
   /**
    * List of coordinates
    */
   public class CoordinatesList extends ArrayList {
      
      public CoordinatesList() {
         super();
      }
      
      @Override
      public boolean contains(final Object o) {
         if (!(o instanceof Coordinate)) {
            return false;
         }
         
         final Coordinate loc = (Coordinate) o;
         for (int i = 0; i < super.size(); i++) {
            final Coordinate test = (Coordinate) super.get(i);
            if (loc.equals(test)) {
               return true;
            }
         }
         return false;
      }
      
      @Override
      public int indexOf(final Object o) {
         if (!(o instanceof Coordinate)) {
            return -1;
         }
         
         final Coordinate loc = (Coordinate) o;
         for (int i = 0; i < super.size(); i++) {
            final Coordinate test = (Coordinate) super.get(i);
            if (loc.equals(test)) {
               return i;
            }
         }
         return -1;
      }
      
      @Override
      public Coordinate get(final int index) {
         final Object o = super.get(index);
         if (o instanceof Coordinate) {
            return (Coordinate) o;
         }
         return null;
      }
   }
   
   /**
    * Comparator for Sparse Matrix coordinates
    */
   private class CoordComparatorRow implements Comparator {
      
      /**
       * compare two coordinates
       * @param t the first coordinate
       * @param t1 the second coordinate
       * @return -1 if t should come first, 1 otherwise
       */
      @Override
      public int compare(final Object t, final Object t1) {
         if (!(t instanceof Coordinate && t1 instanceof Coordinate)) {
            System.exit(-1);
         }
         final Coordinate c1 = (Coordinate) t;
         final Coordinate c2 = (Coordinate) t1;
         
         if (c1.row < c2.row) {
            return -1;
         }
         else if (c1.row > c2.row) {
            return 1;
         }
         else {
            if (c1.col < c2.col) {
               return -1;
            }
            else {
               return 1;
            }
         }
      }
   }
   
   public int num_rows = 0;
   public int num_cols = 0;
   public CoordinatesList coordinates;
   
   /**
    * Constructor for SparseMatrix
    * @param num_rows number of rows in matrix
    * @param num_cols number of cols in matrix
    */
   public SparseMatrix(final int num_rows, final int num_cols) {
      this.num_rows = num_rows;
      this.num_cols = num_cols;
      coordinates = new CoordinatesList();
   }
   
   /**
    * Constructor for SparseMatrix
    * @param copy matrix to copy
    */
   public SparseMatrix(final SparseMatrix copy) {
      num_rows = copy.num_rows;
      num_cols = copy.num_cols;
      coordinates = copy.coordinates;
   }
   
   /**
    * Set an element in the matrix
    * @param row the row of the element
    * @param col the col of the element
    * @param element the value of the element
    */
   public void set_element(final int row, final int col, final double element) {
      // if invalid row or col, throw exception
      if (row > num_rows - 1 || col > num_cols - 1) {
         throw new IndexOutOfBoundsException("row or col was out of bounds set " + row + " " + col + " (" + num_rows + "x" + num_cols + ")");
      }
      
      // if this matrix already contains an element at the location
      if (coordinates.contains(new Coordinate(row, col, element))) {
         // remove the element
         coordinates.remove(coordinates.indexOf(new Coordinate(row, col, element)));
         // if the new element is not zero, add it
         if (element != 0) {
            coordinates.add(new Coordinate(row, col, element));
         }
         // otherwise there is not currently an element at the location
      }
      else {
         // if the new element is not zero, add it
         if (element != 0) {
            coordinates.add(new Coordinate(row, col, element));
         }
      }
      
      // sort the matrix coordinates
      sort_rows();
   }
   
   /**
    * Remove an element from the matrix
    * @param row the row of the element
    * @param col the col of the element
    */
   public void remove_element(final int row, final int col) {
      // if not valid row or col, throw exception
      if (row > num_rows - 1 || col > num_cols - 1) {
         throw new IndexOutOfBoundsException("row or col was out of bounds remove " + row + " " + col);
      }
      
      // remove the element from the coordinates list
      coordinates.remove(coordinates.indexOf(new Coordinate(row, col, 0)));
   }
   
   /**
    * Sort the coordinates using row comparator
    */
   public void sort_rows() {
      Collections.sort(coordinates, new CoordComparatorRow());
   }
   
   /**
    * Represent this matrix as a string
    * @return the string that represents this matrix
    */
   @Override
   public String toString() {
      String s = new String();
      
      s += "num rows: " + num_rows + " num cols: " + num_cols + "\n";
      
      for (int i = 0; i < num_rows; i++) {
         for (int j = 0; j < num_cols; j++) {
            if (coordinates.contains(new Coordinate(i, j, 0))) {
               s += " " + coordinates.get(coordinates.indexOf(new Coordinate(i, j, 0))).element;
            }
            else {
               s += "| |";
            }
         }
         s += "\n";
      }
      
      return s;
   }
   
   /**
    * Matrix multiplication
    * @param other the matrix to be multiplied by
    * @return a sparse matrix that is the result of matrix multiplication
    * @throws Exception 
    */
   public SparseMatrix m_times(final SparseMatrix other) throws Exception {
      // if cannot be multiplied, throw exception
      if (num_cols != other.num_rows) {
         throw new Exception("incompatible matrices");
      }
      
      // Get B as other transpose, this makes it easier since matrices are sorted
      // by rows
      final SparseMatrix B = other.transpose();
      final SparseMatrix C = new SparseMatrix(num_rows, other.num_cols);
      
      // Lists for the rows and cols of A and B
      final ArrayList<CoordinatesList> A_rows = new ArrayList<CoordinatesList>();
      final ArrayList<CoordinatesList> B_cols = new ArrayList<CoordinatesList>();
      double element;
      
      // Get all the rows of A
      for (int i = 0; i < coordinates.size();) {
         final CoordinatesList A_row = new CoordinatesList();
         
         final Coordinate c_A = coordinates.get(i++);
         A_row.add(c_A);
         
         while (i < coordinates.size() && coordinates.get(i).row == c_A.row) {
            A_row.add(coordinates.get(i++));
         }
         
         A_rows.add(A_row);
      }
      
      // Get all the cols of other, which are the rows of B
      for (int j = 0; j < B.coordinates.size();) {
         final CoordinatesList B_col = new CoordinatesList();
         
         final Coordinate c_B = B.coordinates.get(j++);
         B_col.add(c_B);
         
         while (j < B.coordinates.size() && B.coordinates.get(j).row == c_B.row) {
            B_col.add(B.coordinates.get(j++));
         }
         
         B_cols.add(B_col);
      }
      
      // Go through all the rows of A
      for (int i = 0; i < A_rows.size(); i++) {
         // Get a row of A
         final CoordinatesList A_row = A_rows.get(i);
         final int row = A_row.get(0).row;
         // Go through all the cols of other, rows of B
         for (int j = 0; j < B_cols.size(); j++) {
            // Get col of other, row of B
            final CoordinatesList B_col = B_cols.get(j);
            final int col = B_col.get(0).row;
            
            // multiply row and col
            element = multiply(A_row, B_col);
            
            // if the element is not zero, add it to C
            if (element != 0) {
               C.set_element(row, col, element);
            }
         }
      }
      
      return C;
   }
   
   /**
    * Subtract matrices
    * @param B matrix to be subtracted
    * @return result of matrix subtraction
    * @throws Exception 
    */
   public SparseMatrix minus(final SparseMatrix B) throws Exception {
      // if not equal sized matrices, throw exception
      if (B.num_rows != num_rows || B.num_cols != num_cols) {
         throw new Exception("matricies not same size");
      }
      
      final SparseMatrix C = new SparseMatrix(num_rows, num_cols);
      
      // copy this matrix's elements
      for (int i = 0; i < coordinates.size(); i++) {
         C.set_element(coordinates.get(i).row, coordinates.get(i).col, coordinates.get(i).element);
      }
      
      // go through B's elements
      for (int i = 0; i < B.coordinates.size(); i++) {
         // if this matrix has a matching element in B
         if (coordinates.contains(B.coordinates.get(i))) {
            // subtract the two elements
            final Coordinate a = coordinates.get(coordinates.indexOf(B.coordinates.get(i)));
            final double element = a.element - B.coordinates.get(i).element;
            // if the new element is not zero, add it to C
            if (element != 0.0) {
               C.set_element(a.row, a.col, element);
               // if it is zero, remove the entry in C
            }
            else {
               C.remove_element(a.row, a.col);
            }
            // otherwise C didn't have an entry here, so set the element to 0-b(i,j)
         }
         else {
            C.set_element(B.coordinates.get(i).row, B.coordinates.get(i).col, B.coordinates.get(i).element * -1.0);
         }
      }
      
      return C;
   }
   
   /**
    * Element-wise times two matrices
    * @param B matrix to times by
    * @return result of matrix element-wise times
    * @throws Exception 
    */
   public SparseMatrix times(final SparseMatrix B) throws Exception {
      // if the matrices are not the same size, throw exception
      if (num_rows != B.num_rows || num_cols != B.num_cols) {
         throw new Exception("matrices not same size");
      }
      
      final SparseMatrix C = new SparseMatrix(num_rows, num_cols);
      
      // if this matrix has less elements
      if (coordinates.size() < B.coordinates.size()) {
         // go through this matrix's elements
         for (int i = 0; i < coordinates.size(); i++) {
            // if B has a matching element
            if (B.coordinates.contains(coordinates.get(i))) {
               // multiply the two elements together, and put it in C
               final Coordinate b = B.coordinates.get(B.coordinates.indexOf(coordinates.get(i)));
               C.set_element(coordinates.get(i).row, coordinates.get(i).col, b.element * coordinates.get(i).element);
            }
         }
         // otherwise B has less elements
      }
      else {
         // go through B's elements
         for (int i = 0; i < B.coordinates.size(); i++) {
            // if this matrix has a matching element
            if (coordinates.contains(B.coordinates.get(i))) {
               // multiply the two elements together, and put it in C
               final Coordinate a = coordinates.get(coordinates.indexOf(B.coordinates.get(i)));
               C.set_element(B.coordinates.get(i).row, B.coordinates.get(i).col, a.element * B.coordinates.get(i).element);
            }
         }
      }
      
      return C;
   }
   
   /**
    * Element-wise divide two matrices
    * @param B divisor
    * @return result of element-wise divide
    * @throws Exception 
    */
   public SparseMatrix divide(final SparseMatrix B) throws Exception {
      // if matrices are not same size, throw exception
      if (num_rows != B.num_rows || num_cols != B.num_cols) {
         throw new Exception("matrices not same size");
      }
      
      final SparseMatrix C = new SparseMatrix(num_rows, num_cols);
      
      // go through this elements coordinates
      for (int i = 0; i < coordinates.size(); i++) {
         // if B has a matching element
         if (B.coordinates.contains(coordinates.get(i))) {
            // add epsilon to b, and divide, set element in C
            final Coordinate b = B.coordinates.get(B.coordinates.indexOf(coordinates.get(i)));
            C.set_element(coordinates.get(i).row, coordinates.get(i).col, coordinates.get(i).element / (b.element + .01));
            // if B does not have a matching element, divide by epsilon
         }
         else {
            C.set_element(coordinates.get(i).row, coordinates.get(i).col, coordinates.get(i).element / .01);
         }
      }
      
      return C;
   }
   
   private double multiply(final CoordinatesList A_coords, final CoordinatesList B_coords) {
      double sum = 0;
      final int row = B_coords.get(0).row;
      // go through A's coordinates
      for (int i = 0; i < A_coords.size(); i++) {
         // if B has a matching coordinate
         if (B_coords.contains(new Coordinate(row, A_coords.get(i).col, 0))) {
            // multiply them, add to already existing sum
            sum += B_coords.get(B_coords.indexOf(new Coordinate(row, A_coords.get(i).col, 0))).element * A_coords.get(i).element;
         }
      }
      
      // return dot product of A row and B col
      return sum;
   }
   
   /**
    * Transpose of matrix
    * @return transpose of this matrix
    */
   public SparseMatrix transpose() {
      final SparseMatrix A = new SparseMatrix(num_cols, num_rows);
      
      // for all the elements in this matrix
      for (int i = 0; i < coordinates.size(); i++) {
         // flip the row and col and add the element to A
         final Coordinate a = coordinates.get(i);
         A.set_element(a.col, a.row, a.element);
      }
      
      return A;
   }
   
   /**
    * The Frobenius norm of this matrix
    * @return the Frobenius norm of this matrix
    */
   public double frobeniusNorm() {
      double norm = 0;
      
      // go through all the coordinates
      for (int i = 0; i < coordinates.size(); i++) {
         // get the square of each element, added to the overall norm
         final double element = coordinates.get(i).element;
         norm += element * element;
      }
      
      return Math.sqrt(norm);
   }
   
   /**
    * Randomize this matrix
    */
   public void randomize() {
      final Random rand = new Random();
      
      // put a random element in every coordinate in this matrix
      for (int i = 0; i < num_rows; i++) {
         for (int j = 0; j < num_cols; j++) {
            set_element(i, j, rand.nextDouble());
         }
      }
   }
}
